package common.utils;

/**
 * 并查集
 */
public class UnionFind {
    int[] parent;

    public UnionFind(int n){
        parent = new int[n];
        for (int i = 0; i < n; i++){
            parent[i] = i;
        }

    }

    //将index2并入到index1
    // 1 - union successfully, 0 - union failed
    public int union(int index1, int index2){
        int index1_root = find(index1);
        int index2_root = find(index2);
        if (index1_root == index2_root){
            return 0;
        } else {
            parent[index2_root] = find(index1_root);
            return 1;
        }

    }
    //查找index的帮主，同时优化并查集
    public int find(int index){
        if (parent[index] != index){
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
}
